翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Narayana triangle : ウィキペディア英語版
Narayana number
In combinatorics, the Narayana numbers ''N''(''n'', ''k''), ''n'' = 1, 2, 3 ..., 1 ≤ ''k'' ≤ ''n'', form a triangular array of natural numbers, called Narayana triangle, that occur in various counting problems. They are named for T.V. Narayana (1930–1987), a mathematician from India.
The Narayana numbers can be expressed in terms of binomial coefficients:
: N(n,k) = \frac.
An example of a counting problem whose solution can be given in terms of the Narayana numbers ''N''(''n'', ''k''), is the number of expressions containing ''n'' pairs of parentheses which are correctly matched and which contain ''k'' distinct nestings. For instance, ''N''(4, 2) = 6 as with four pairs of parentheses six sequences can be created which each contain two times the sub-pattern '()':
()((())) (())(()) (()(())) ((()())) ((())()) ((()))()
From this example it should be obvious that ''N''(''n'', 1) = 1, since the only way to get a single sub-pattern '()' is to have all the opening parentheses in the first n positions, followed by all the closing parentheses. Also ''N''(''n'', ''n'') = 1, as distinct nestings can be achieved only by the repetitive pattern ()()() ... (). More generally, it can be shown that the Narayana triangle is symmetric: ''N''(''n'', ''k'') = ''N''(''n'', ''n'' − ''k'' + ''1'').
The first eight rows of the Narayana triangle read:
''k'' = 1 2 3 4 5 6 7 8
''n'' = 1 1
2 1 1
3 1 3 1
4 1 6 6 1
5 1 10 20 10 1
6 1 15 50 50 15 1
7 1 21 105 175 105 21 1
8 1 28 196 490 490 196 28 1
The sum of the rows in this triangle equal the Catalan numbers:
:N(n,1) + N(n,2) + N(n,3) + \cdots + N(n,n) = C_n.
To illustrate this relationship, the Narayana numbers also count the number of paths from (0, 0) to (2''n'', 0), with steps only northeast and southeast, not straying below the ''x''-axis, with ''k'' peaks.
The following figures represent the Narayana numbers ''N''(4, ''k''):
The sum of ''N''(4, ''k'') is 1 + 6 + 6 + 1, or 14, which is the same as Catalan number ''C''4. This sum coincides with the interpretation of Catalan numbers as the number of monotonic paths along the edges of an ''n'' × ''n'' grid that do not pass above the diagonal.
== Partitions ==

In the study of partitions, we see that in a set containing n elements, we may partition that set in B_n different ways, where B_n is the nth Bell number. Furthermore, the number of ways to partition a set into exactly k blocks we use the Stirling numbers S(n,k). Both of these concepts are a bit off-topic, but a necessary foundation for understanding the use of the Narayana numbers. In both of the above two notions crossing partitions are accounted for.
To reject the crossing partitions and count only the noncrossing partitions, we may use the Catalan numbers to count the non-crossing partitions of all n elements of the set, C_n. To count the non-crossing partitions in which the set is partitioned in exactly k blocks, we use the Narayana number N(n,k).

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Narayana number」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.